package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2385. 感染二叉树需要的总时间
 * <p>
 * 给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。
 *
 * 每分钟，如果节点满足以下全部条件，就会被感染：
 *
 * 节点此前还没有感染。
 * 节点与一个已感染节点相邻。
 * 返回感染整棵树需要的分钟数。
 * User:Mr.Du
 * Date:2024/4/24
 * Time:9:57
 */
public class AmountOfTime {

    /**
     * 计算从指定起始节点开始遍历树的时间量
     * @param root 树的根节点
     * @param start 遍历的起始节点的值
     * @return 从起始节点开始遍历到所有节点的时间量
     */
    public int amountOfTime(TreeNode root, int start) {
        // 使用邻接表存储树的结构
        List<Integer>[] list = new List[100001];
        Arrays.setAll(list, e -> new ArrayList<>());

        // 广度优先搜索遍历树，构建邻接表
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode x = queue.poll();
                if(x.left != null){
                    list[x.val].add(x.left.val);
                    list[x.left.val].add(x.val);
                    queue.offer(x.left);
                }
                if(x.right != null){
                    list[x.val].add(x.right.val);
                    list[x.right.val].add(x.val);
                    queue.offer(x.right);
                }
            }
        }

        // 使用集合记录已经访问过的节点
        Set<Integer> set = new HashSet<>();
        // 使用队列进行广度优先搜索
        Queue<Integer> q = new ArrayDeque<>();
        int res = 0; // 记录遍历的时间量
        q.offer(start);

        // 广度优先搜索遍历邻接表
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                int p = q.poll();
                for(int x : list[p]){
                    // 如果节点未被访问过，则加入队列，标记为已访问
                    if(!set.contains(x)){
                        set.add(x);
                        q.offer(x);
                    }
                }
                set.add(p);
            }
            res++;
        }

        // 返回遍历的时间量减去起始节点本身的时间，因为题目要求的是遍历过程的时间
        return res - 1;
    }


    int ans, start;
    /**
     * 深度优先搜索算法来遍历树以寻找特定起点的最长路径。
     * @param root 树的根节点。
     * @return 返回从根节点到叶子节点的最长路径中，起点到终点的最长路径长度。
     */
    public int dfs(TreeNode root){
        if(root==null) return 0; // 当遍历到叶子节点时返回0
        int l = dfs(root.left); // 递归遍历左子树
        int r = dfs(root.right); // 递归遍历右子树

        // 判断当前节点是否为起点，如果是，则更新最长路径长度
        if(root.val == start) {
            ans = Math.max(ans,Math.max(l, r));
            return -1; // 返回一个特殊值标识当前节点为起点
        }

        // 计算当前节点为中间节点时，左右子树的最大路径和
        if(l >= 0 && r >= 0){
            return Math.max(l, r) + 1;
        }else if(l < 0){
            ans = Math.max(ans, r-l);
            return l - 1;
        }else{
            ans = Math.max(ans, l-r);
            return r - 1;
        }
    }

}
